Rotate Array



In [1]:

    
import sys; sys.path.append('../..')
from puzzles import leet_puzzle
leet_puzzle('rotate-array')









    




Source : https://leetcode.com/problems/rotate-array
Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4]. 
Note:

Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

[show hint]
Hint:

Could you do it in-place with O(1) extra space?

Related problem: Reverse Words in a String II
Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.






Array





 (M) Rotate List
 (M) Reverse Words in a String II



In [4]:

    
n, k = 7, 4
example_array = list(range(n))
example_array









    Out[4]:





[0, 1, 2, 3, 4, 5, 6]

Simple Solution

The simplest solution splits the array at the point to rotate, and constructs a new array using the two parts.



In [5]:

    
def rotate_simple(input_array, order):
    order %= len(input_array)
    return input_array[order:] + input_array[:order]

rotate_simple(example_array, k)









    Out[5]:





[4, 5, 6, 0, 1, 2, 3]



In [9]:

    
%%timeit
rotate_simple(example_array, k)









    



The slowest run took 6.15 times longer than the fastest. This could mean that an intermediate result is being cached 
1000000 loops, best of 3: 621 ns per loop

This solution has both time and space complexity of O(n).

Bubble Rotate

However if we want to rotate a large array in place (without creating a new array), the solution above is inefficient. The time complexity is O(n), dependant only on the size of the input array, but the space complexity is also O(n) since we need to create a new array with the rotated elements. By applying a similar algorithm to bubble sort we can perform the rotation in place.



In [10]:

    
def rotate_bubble_inplace(input_array, order):
    order %= len(input_array)
    for i in range(order):
        for j in range(len(input_array)):
            input_array[j], input_array[j - 1] = input_array[j - 1], input_array[j]
    return input_array
            
example_array2 = list(example_array)
rotate_bubble_inplace(example_array2, k)









    Out[10]:





[4, 5, 0, 1, 2, 3, 6]



In [11]:

    
%%timeit
rotate_bubble_inplace(example_array, k)









    



100000 loops, best of 3: 8.46 µs per loop

However, although the space complexity is now O(1), the time complexity is O(n * k). It would be good to find a solution that has O(1) space complexity and O(n) time complexity.

Reverse Rotate

Another way of rotating the array is to split the array into two sub arrays at the point of rotation. Each subarray is reversed, before rotating the entire array. This solution achieves O(1) space complexity and O(n).



In [12]:

    
def rotate_reverse_inplace(input_array, order):
    length = len(input_array)
    order = -order % length
    split_location = length - order
    input_array[:split_location] = reversed(input_array[:split_location])
    input_array[split_location:] = reversed(input_array[split_location:])
    input_array.reverse()
    return input_array

example_array2 = list(example_array)
rotate_reverse_inplace(example_array2, k)









    Out[12]:





[4, 5, 6, 0, 1, 2, 3]



In [13]:

    
%%timeit
rotate_reverse_inplace(example_array, k)









    



The slowest run took 5.80 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 2.1 µs per loop